package org.example.SolutionNew002;

import java.util.HashSet;
import java.util.Set;

public class LinkedList01 {
    public static void main(String[] args) {
        LinkedList01 obj = new LinkedList01();
        ListNode a = new ListNode(1);
        System.out.println(obj.getIntersectionNode(a, a).val);
    }

    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode res=null;
        if(headA==null||headB==null) return res;
        //对于两个链表能否先控制长度
        int aSize=0,bSize=0;
        ListNode a=headA,b=headB;
        while(a!=null){
            aSize++;
            a=a.next;
        }
        while(b!=null){
            bSize++;
            b=b.next;
        }
        a=headA;b=headB;
        if(aSize>bSize){
            for(int i=0;i<aSize-bSize;i++){
                a=a.next;
            }
        }else if(bSize>aSize){
            for(int i=0;i<bSize-aSize;i++){
                b=b.next;
            }
        }
        int size=Math.min(aSize,bSize);
        for(int i=0;i<size;i++){
            if(a==b){
                return a;
            }
            a=a.next;
            b=b.next;
        }
        return res;
    }

    //哈希表不错
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode res=null;
        if(headA==null||headB==null) return res;
        Set<ListNode> set=new HashSet<>();
        while(headA!=null){
            set.add(headA);
            headA=headA.next;
        }
        while(headB!=null){
            if(set.contains(headB)){
                return headB;
            }
            headB=headB.next;
        }
        return res;
    }

    //偏数学思想，让两个头节点都走m+n步，走完或走完之前一定能遇到相交点，或点不存在
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        ListNode a=headA,b=headB;
        while(a!=b){
            a = a==null?headB:a.next;
            b = b==null?headA:b.next;
        }
        return a;
    }
}
